package com.stanley.alogrithm.string;

public class LongestCommonPrefix {

    public static void main(String[] args) {
        //String[] strs = {"fellowxxx", "fellow", "fellow2", "fellowkkbcd", "fekkk", "fello"};
        LongestCommonPrefix lcp = new LongestCommonPrefix();
        String c = lcp.longestCommonPrefix(new String[] {"dog","racecar","car"});
        System.out.println("result:" + c);
    }

    public String longestCommonPrefix(String[] strs) {
        String result = "";
        if (strs == null || strs.length == 0) {
            return result;
        }
        if (strs.length < 2) {
            return strs[0];
        }
        // [0, pivot -1], [pivot, length - 1]
        result = computeLCP(strs, 0, strs.length - 1);
        return result;
    }

    private String computeLCP(String[] strs, int start, int end) {
        if ( end == start) {
            return strs[end];
        }
        if ( end - start < 0) {
            return "";
        }
        if (end - start < 2) {
            return getCommonPrefix(strs[start], strs[end]);
        }
        int pivot = (start + end) / 2;
        System.out.println(String.format("start:%d, pivot:%d, end:%d ", start, pivot, end));
        String subLcp = computeLCP(strs, start, pivot);
        String subLcp2 = computeLCP(strs, pivot + 1, end);

        return getCommonPrefix(subLcp, subLcp2);
    }

    private String getCommonPrefix(String str1, String str2) {
        if (str1 == null || str2 == null) {
            return "";
        }
        int minLen = Math.min(str1.length(), str2.length());
        if (minLen < 1) {
            return "";
        }
        int subIndex = 0;
        String prefix1 = str1.substring(0, subIndex + 1), prefix2 = str2.substring(0, subIndex + 1);

        while (prefix1.equals(prefix2)) {
            subIndex++;
            if (subIndex + 1 <= minLen) {
                prefix1 = str1.substring(0, subIndex + 1);
                prefix2 = str2.substring(0, subIndex + 1);
            } else {
                break;
            }
        }
        return str1.substring(0, subIndex);
    }
}
